<template>
  <ExamPaper :items="paper" :name="title" @update:answers="(val) => (finalAnswers = val)" />
</template>

<script setup>
import { ref, onMounted, computed } from "vue";
import ExamPaper from "@/components/ExamPaper.vue";
// 使用路由meta中的name作为标题
import { useRoute } from "vue-router";
const route = useRoute();
const title = computed(() => {
  return route.meta.title || "算法题库";
});

const paper = ref([
  {
    question: `
        最优优先搜索
        778. 水位上升的泳池中游泳
        困难
        相关标签
        premium lock icon
        相关企业
        提示
        在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

        当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

        你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

        

        示例 1:
        <img src="https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg">


        输入: grid = [[0,2],[1,3]]
        输出: 3
        解释:
        时间为0时，你位于坐标方格的位置为 (0, 0)。
        此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
        等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置
        示例 2:
        <img src="https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg">


        输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
        输出: 16
        解释: 最终的路线用加粗进行了标记。
        我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
        

        提示:

        n == grid.length
        n == grid[i].length
        1 <= n <= 50
        0 <= grid[i][j] < n2
        grid[i][j] 中每个值 均无重复
        `,
    answer: `
        function deal1(grid) {
          const maxRow = grid.length;
          const maxCol = grid[0].length;
          const minStartVal = maxRow + maxCol - 2;
          const valueArray = new Array(maxCol * maxRow).fill(false);
          const visted = new Set();
          let result;
          valueArray[0] = [0, 0];
          function step([row, col], startVal) {
            if (
              row < 0 ||
              col < 0 ||
              row >= maxRow ||
              col >= maxCol ||
              visted.has(grid[row][col])
            ) {
              
            } else if (startVal < grid[row][col]) {
              valueArray[grid[row][col]] = [row, col];
              
            } else {
              visted.add(grid[row][col]);
              if (row == maxRow - 1 && col == maxCol - 1) {
                result = startVal;
              }
              step([row + 1, col], startVal);
              step([row, col + 1], startVal);
              step([row - 1, col], startVal);
              step([row, col - 1], startVal);
              
            }
          }
          let findIndex;
          function hasPendding() {
            findIndex = valueArray.findIndex((item) => item);
            return findIndex;
          }
          while (hasPendding()>-1 && !result) {
            step(valueArray[findIndex], minStartVal>findIndex?minStartVal:findIndex);
            valueArray[findIndex] = false;
          }
          console.log(result||minStartVal)
          return result||minStartVal;
        }
        deal1([
          [0, 1, 2, 3, 4],
          [24, 23, 22, 21, 5],
          [12, 13, 14, 15, 16],
          [11, 17, 18, 19, 20],
          [10, 9, 8, 7, 6],
        ])
        `,
    remark: `
        // 手写最小堆，只支持我们需要的接口
        class MinHeap {
          constructor() {
            this.heap = [];
          }
          size() {
            return this.heap.length;
          }
          enqueue(val, r, c) {
            this.heap.push({ key: val, row: r, col: c });
            this._up(this.heap.length - 1);
          }
          dequeue() {
            const top = this.heap[0];
            const last = this.heap.pop();
            if (this.heap.length) {
              this.heap[0] = last;
              this._down(0);
            }
            return top;
          }
          _up(i) {
            while (i > 0) {
              const p = (i - 1) >> 1;
              if (this.heap[i].key >= this.heap[p].key) break;
              [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
              i = p;
            }
          }
          _down(i) {
            const n = this.heap.length;
            while (true) {
              let l = (i << 1) + 1;
              let r = l + 1;
              let smallest = i;
              if (l < n && this.heap[l].key < this.heap[smallest].key) smallest = l;
              if (r < n && this.heap[r].key < this.heap[smallest].key) smallest = r;
              if (smallest === i) break;
              [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
              i = smallest;
            }
          }
        }

        /* ---------- 下面是你原来的函数，一字不改变量名 ---------- */
        function deal1(grid) {
          const maxRow = grid.length;
          const maxCol = grid[0].length;
          const minStartVal = maxRow + maxCol - 2;
          // 用自写堆替换第三方
          const pq = new MinHeap();
          pq.enqueue(grid[0][0], 0, 0);

          const vistedCoord = Array(maxRow)
            .fill(null)
            .map(_ => Array(maxCol).fill(false));

          let result;

          function step([row, col], startVal) {
            if (
              row < 0 ||
              col < 0 ||
              row >= maxRow ||
              col >= maxCol ||
              vistedCoord[row][col]
            ) {
              return;
            }
            if (startVal < grid[row][col]) {
              pq.enqueue(grid[row][col], row, col);
            } else {
              vistedCoord[row][col] = true;
              if (row === maxRow - 1 && col === maxCol - 1) {
                result = startVal;
                return;
              }
              step([row + 1, col], startVal);
              step([row, col + 1], startVal);
              step([row - 1, col], startVal);
              step([row, col - 1], startVal);
            }
          }

          while (pq.size() && !result) {
            const { key: h, row: r, col: c } = pq.dequeue();
            const useVal = minStartVal > h ? minStartVal : h;
            step([r, c], useVal);
          }

          console.log(result || minStartVal);
          return result || minStartVal;
        }

        /* ---------- 测试 ---------- */
        deal1([
          [0, 1, 2, 3, 4],
          [24, 23, 22, 21, 5],
          [12, 13, 14, 15, 16],
          [11, 17, 18, 19, 20],
          [10, 9, 8, 7, 6],
        ]);

        下面给你逐行拆解 _up 和 _down 到底干了什么，让你一眼看出它为什么只走“一条路径”，而不是“整个数组重新排序”。

        一、_up（插入时把新元素“上浮”到正确位置）
        JavaScript
        复制
        _up(i) {              // i 是刚插到末尾的下标
          while (i > 0) {
            const p = (i - 1) >> 1;     // 父节点下标，位运算比 Math.floor 快
            if (this.heap[i].key >= this.heap[p].key) break; // 父子顺序正确，停
            [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]]; // 交换
            i = p;                      // 继续向上
          }
        }
        流程图（举例）
        把 1 插到末尾 idx=9：
        复制
                2
              /     \
            5       3
            / \     / \
          7  9   8   4
          / \
        10  1←idx=9
        第 1 次循环：i=9，父 p=4，1<9 → 交换，高度 +1；
        第 2 次循环：i=4，父 p=1，1<5 → 交换，高度 +1；
        第 3 次循环：i=1，父 p=0，1<2 → 交换，高度 +1；
        第 4 次循环：i=0 无父，停。
        总共 3 次交换，路径长度 ⌊log₂10⌋=3，只动了 3 个节点，其余 6 个节点看都没看。
        二、_down（弹出堆顶后把末尾元素“下沉”到正确位置）
        JavaScript
        复制
        _down(i) {
          const n = this.heap.length;
          while (true) {
            let l = (i << 1) + 1;   // 左子
            let r = l + 1;          // 右子
            let smallest = i;
            if (l < n && this.heap[l].key < this.heap[smallest].key) smallest = l;
            if (r < n && this.heap[r].key < this.heap[smallest].key) smallest = r;
            if (smallest === i) break;          // 顺序正确，停
            [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
            i = smallest;                       // 继续向下
          }
        }
        流程图（接上例）
        弹出 1 后把末尾 10 放到栈顶：
        复制
                10
              /     \
            2       3
            / \     / \
          7  5   8   4
        第 1 次循环：i=0，左右子 2,3 都比 10 小，选最小 2 → 交换；
        第 2 次循环：i=1，左右子 7,5 都比 10 小，选最小 5 → 交换；
        第 3 次循环：i=4，无子，停。
        又只动了 3 个节点，其余节点原地不动。
        三、复杂度小结
        表格
        复制
        操作	最坏交换/比较次数	涉及节点数	路径长度
        _up	⌊log₂k⌋	log₂k+1	自底向上一条链
        _down	⌊log₂k⌋	log₂k+1	自顶向下一条链
        k 为当前堆大小，本题最大 2500，路径长度 ≤11。
        因此最小堆根本不是“重新排序”，它只沿着一条高度为 log k 的链做局部修复，其余元素完全不动，这就是它能把“取最小”降到 O(log N) 的根本原因。

        这个逻辑是 down来保证处于一层的数据一定比下一层的大。 所以up 只需要单链路对比就可以了。
        `,
  },
  {
    question: ` 
    深度优先搜索（困难）
    332. 重新安排行程
    相关标签
    premium lock icon
    相关企业
    给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

    所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

    例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
    假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

    

    示例 1：
    <img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg" style="width: 382px; height: 222px;">

    输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
    输出：["JFK","MUC","LHR","SFO","SJC"]
    示例 2：
    <img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg" style="width: 222px; height: 230px;">

    输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
    解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
    

    提示：

    1 <= tickets.length <= 300
    tickets[i].length == 2
    fromi.length == 3
    toi.length == 3
    fromi 和 toi 由大写英文字母组成
    fromi != toi
    `,
    answer: `
    function deal2(tickets = []) {
      function getCharValue(str){
        const charMap = new Map([
          ['A',1],
          ['B',2],
          ['C',3],
          ['D',4],
          ['E',5],
          ['F',6],
          ['G',7],
          ['H',8],
          ['I',9],
          ['J',10],
          ['K',11],
          ['L',12],
          ['M',13],
          ['N',14],
          ['O',15],
          ['P',16],
          ['Q',17],
          ['R',18],
          ['S',19],
          ['T',20],
          ['U',21],
          ['V',22],
          ['W',23],
          ['X',24],
          ['Y',25],
          ['Z',26]
        ])
        let result = ''
        for(let i=0;i<str.length;i++){
          result += charMap.get(str[i])
        }
        return result
      }
      const mapObj = {};
      tickets.forEach(item => {
        if(!mapObj[item[0]]){
          mapObj[item[0]] = [];
        }
        mapObj[item[0]].push(item[1]);
      })
      const ticketsLength = tickets.length;
      const visited = new Set();
      const result = [];
      function step(val='JFK',path=['JFK']){
        const nextValArr = mapObj[val];
        if(nextValArr){
          if(nextValArr.length>1){
            nextValArr.sort((a,b)=>{
              return getCharValue(a)<getCharValue(b)?-1:1
            });
          }
          nextValArr.forEach(nextVal=>{
            const visitedItem = \`\${val}-\${nextVal}\`;
            if(!visited.has(visitedItem)){
              visited.add(visitedItem);
              step(nextVal,[...path,nextVal]);
              visited.delete(visitedItem);
            }else{
              if(ticketsLength+1===path.length){
                result.push(path);
              }
            }
          })
        }else{
          if(ticketsLength+1===path.length){
            result.push(path);
          }
        }
      }
      step();
      console.log(result)
      return result[0];
    }
    // 修正后
    function deal2(tickets = []) {
      const mapObj = {};
      tickets.forEach(item => {
        if (!mapObj[item[0]]) mapObj[item[0]] = [];
        mapObj[item[0]].push(item[1]);
      });
      for (const arr of Object.values(mapObj)) arr.sort((a, b) => a.localeCompare(b));

      const ptr = {};
      for (const f in mapObj) ptr[f] = 0;

      const ticketsLength = tickets.length;
      let result = null;               // 只要这一条

      function step(val = 'JFK', path = ['JFK']) {
        if (result) return;            // 已找到，直接剪枝
        if (path.length === ticketsLength + 1) {
          result = path.slice();       // 命中，保存
          return;
        }
        const nextValArr = mapObj[val];
        if (!nextValArr) return;

        let i = ptr[val];
        while (i < nextValArr.length) {
          ptr[val] = i + 1;
          step(nextValArr[i], [...path, nextValArr[i]]);
          if (result) return;          // 上层已经找到，不再继续
          i = ptr[val];                // 继续试下一条边
        }
      }

      step();
      return result;
    }
    `,
    remark: `
    你这段代码已经能跑通大部分用例，思路也很清晰：
    用邻接表把图建出来；
    对同一出发点的所有目的地按“字典序”排序；
    用 DFS + 回溯把每条边恰好走一次，最先凑满 tickets.length+1 个节点的路径立即返回。
    但在面试或提交时还会暴露出 4 个硬伤，下面逐条指出并给出修改建议。
    字典序排序成本太高
    你每次递归都要把 nextValArr 重新 sort，而且用 getCharValue 把 3 位机场代码先转成数字串再比较，单次排序复杂度从 O(k log k) 上升到 O(k·3·log k)。
    改：
    预处理阶段就把每个出发点的目的地数组按字符串字典序排好；
    直接 a.localeCompare(b) 即可，不用自己写映射。
    回溯框架不是“最先找到即最优”
    题目只要字典序最小的一条路线，而你把所有完整路径都 result.push(path) 后再 return result[0]，相当于把整棵搜索树跑完再挑最小，最坏 300! 条路径显然会超时。
    改：
    借鉴 Hierholzer／欧拉路径思路：
    只要当前路径长度 == tickets.length+1，立即 return true 并终止全部搜索；
    或者像官方题解那样后序插入链表，第一次 DFS 结束就得到逆序结果，无需比较。
    去重方式不对
    你用 visitedItem = val−{nextVal} 做边级去重，但同一段航线可能有多张票（例如 [["JFK","ATL"],["JFK","ATL"]]），Set 会把第二张票也挡住。
    改：
    给邻接表每个目的地再配一个“剩余票数”计数（Map<string, number> 或 PriorityQueue + used[]）；
    每次 --cnt，回溯时 ++cnt，而不是用全局 Set。
    结果数组只取 result[0] 可能为空
    当图刚好是一条链时，你的 step 在叶子节点才把路径 push，而回溯过程中没有立即返回，导致 result 里可能没有任何元素就执行到 return result[0]，出现 undefined。
    改：
    一旦找到合法路径立刻返回，不要收集全部再挑。
    参考实现（JavaScript 版，按上述思路修正）
    JavaScript
    复制
    function findItinerary(tickets) {
      // 1. 建图 & 排序
      const g = new Map();
      for (const [from, to] of tickets) {
        if (!g.has(from)) g.set(from, []);
        g.get(from).push(to);
      }
      for (const arr of g.values()) arr.sort((a, b) => a.localeCompare(b));

      const res = [];                 // 后序插入，最后要 reverse
      function dfs(u) {
        const nxt = g.get(u);
        while (nxt && nxt.length) {   // 2. 每次弹第一个（最小字典序）
          const v = nxt.shift();      // 3. 边被“用掉”
          dfs(v);
        }
        res.push(u);                  // 4. 后序收集
      }
      dfs('JFK');
      return res.reverse();
    }
    时间复杂度：O(E log E) 预处理排序 + O(E) 单次 DFS；
    空间复杂度：O(V+E)。
    总结
    你的原始代码结构已经具备“图＋DFS”雏形，只要把排序提前、去重改为票数计数、并在第一次凑满路径时立即返回，就能从“能跑”升级为“一次提交通过”。继续加油！
  `,
  },
  {
    question: `
    Search
    22. 括号生成
    中等
    相关标签
    premium lock icon
    相关企业
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

    

    示例 1：

    输入：n = 3
    输出：["((()))","(()())","(())()","()(())","()()()"]
    示例 2：

    输入：n = 1
    输出：["()"]
    

    提示：

    1 <= n <= 8
    `,
    answer: `
    function deal3(num){
      const result = [];
      function step(path='',pathArr = [],leftNum,rightNum){
        if(leftNum == 0 && rightNum == 0){
          result.push(path)
          return
        }
        if(leftNum>0){
          step(path+'(',pathArr.concat('('),leftNum-1,rightNum)
        }
        if(rightNum>0 && rightNum>leftNum){
          step(path+')',pathArr.concat(')'),leftNum,rightNum-1)
        }
      }
      step('',[],num,num)
      console.log(result)
      return result
    }
    `,
    remark: `
    和判断是不是正确闭合不同，这个是生成所有可能的括号组合
    而且是同一种括号。所以不用用出栈的办法比对末端未消费的左括号是不是对的上有括号
    只需要知道左右括号的个数就行，不需要知道左右括号的位置。只需要保证右括号的个数大于左括号的个数就行
    `,
  },
]);



onMounted(() => {
});

const finalAnswers = ref([]); // 实时收集到的答案
</script>
